Skip to main content

Two Pointer

Patterns

Running from both ends of an array​

  • Having two pointers at left and right end of array, then moving them to the center while processing something with them.

When to use

  • This works particularly well for sorted array

  • Need to find a pair of values

  • Trapping Rain Water - https://leetcode.com/problems/trapping-rain-water/

    • Have to be able to find out the mathematic equation for each position
    • The remaining is just optimizing how to find maxLeft, maxRight in the most efficient way
def trap(self, height: List[int]) -> int:
    # curTrap = min(left, right) - height[i]
    left, right = 0, len(height) - 1
    res = 0
    leftMax, rightMax = 0, 0
    while left < right:
        if height[left] < height[right]:
            leftMax = max(leftMax, height[left])
            res += leftMax - height[left]
            left += 1
        else:
            rightMax = max(rightMax, height[right])
            res += rightMax - height[right]
            right -= 1
    
    return res

Fast and Slow Pointer​

  • Usually used in [[6. Linked List]] for cycle detection

Same Direction​

  • Both pointers move in the same direction, but at different paces or with different conditions.

When to use

  • If need to process elements sequentially
  • If need to modify array in-place

Merge 2 arrays​

  • Will be given 2 arrays or lists, then have to process them with individual pointers

https://leetcode.com/problems/add-strings

  • Pretty good questions on practicing adding 2 string numbers
 def addStrings(self, num1: str, num2: str) -> str:
    l1, l2 = len(num1) - 1, len(num2) - 1
    rem = 0
    res = []

    while l1 >= 0 or l2 >= 0 or rem:
        val1 = int(num1[l1]) if l1 >= 0 else 0
        val2 = int(num2[l2]) if l2 >= 0 else 0
        total = val1 + val2 + rem
        rem = total // 10
        res.insert(0, str(total % 10))
        l1 -= 1
        l2 -= 1
    
    return ''.join(res)

Variants

Next Permutation Theory​

https://leetcode.com/problems/next-permutation

  • This problem is not usual two pointer problem
  • The only reason we call it two pointer is because we want to swap 2 value in place which we have to use 2 pointer
  • Otherwise, this is a math problem
  • The idea is similar to permute a number to get the next greater value
    • First we have to find a value we want to swap and a second value to swap it with
    • Then we sort the rest to ensure that we have smallest right part possible
  • [[Useful math#^2b285a | Next greater number theory]]
 def nextPermutation(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    swapLeft = len(nums) - 2
    while swapLeft >= 0 and nums[swapLeft] >= nums[swapLeft + 1]:
        swapLeft -= 1
    
    if swapLeft < 0:
        return nums.reverse()
    
    swapRight = nums[swapLeft+1:].index(max(nums[swapLeft+1:]))
    swapRightVal = float('inf')
    for i in range(swapLeft+1, len(nums)):
        if nums[i] > nums[swapLeft] and nums[i] < swapRightVal:
            swapRightVal = nums[i]
            swapRight = i
    
    nums[swapLeft], nums[swapRight] = nums[swapRight], nums[swapLeft]
    nums[swapLeft+1:] = sorted(nums[swapLeft+1:])

https://leetcode.com/problems/next-greater-element-iii

  • Same as above
 def nextGreaterElement(self, n: int) -> int:
    n = list([int(i) for i in str(n)])

    swapLeft = len(n) - 2
    while swapLeft >= 0 and n[swapLeft] >= n[swapLeft+1]:
        swapLeft -= 1
    
    if swapLeft < 0:
        return -1
    
    swapRight = len(n) - 1
    swapRightVal = float('inf')

    for i in range(swapLeft+1, len(n)):
        if n[i] > n[swapLeft] and n[i] < swapRightVal:
            swapRight = i
            swapRightVal = n[i]
    
    n[swapLeft], n[swapRight] = n[swapRight], n[swapLeft]
    n[swapLeft+1:] = sorted(n[swapLeft+1:])

    res = int(''.join([str(i) for i in n]))
    if res > 2**31 - 1:
        return -1
    return res